There are approximately 255 nanoseconds in a year. This means that any high-speed circuit running at a clock rate of 1 GHz would need at least a 55-bit counter to log events with respect to time for one year. Situations involving such long-period counters such as long-term environmental monitoring or long-term simulations using application-specific computational circuits are readily imagined. Ordinary binary counters are problematic in that they engender long propagation delays, thus slowing the entire circuit. As shown in FIG. 1, the conventional counter generates overall carry propagation delays between each bit that slow the overall clock speed of the circuit. In a 55-bit counter, this propagation delay caused by the carry is significant and unacceptable.
This problem can be mitigated by using a “carry-look-ahead” structure as found in conventional addition circuits, but the problem still remains and the circuits require a substantial amount of both wiring and logic gates.
Another possibility for a long-period high-speed counter is the linear feedback shift register or LFSR, as shown in FIG. 2. The main problem with the LFSR is that the counting sequence is pseudorandom, and it is not possible to determine the actual count from the sequence directly, but rather the count must be simulated. For long-period applications this is highly problematic. From the standpoint of circuit implementation, however, it is a highly desirable circuit due to most bits having direct connections and not requiring any carry logic. An LFSR takes less resources and frequently runs much faster than a conventional counter.
A linear feedback shift register generally consists of two or more D-type flip-flops and one or more exclusive-OR (XOR) or exclusive-NOR (XNOR) gates. The flip-flops form a shift register. A shift register is a device whose identifying function is to shift its contents into adjacent positions within the register or, in the case of the position on the end, out of the register. The position on the other end is left empty unless some new content is shifted into the register. The contents of a shift register are usually binary, that is, ones and zeroes. If a shift register contains the bit pattern 1101, a shift, in this case to the right, would result in the contents being 0110; another shift yields 0011. Whether it shifts right or left does not really matter and is usually determined by the requirements of the circuit that the LFSR is driving or the method that it is being constructed by. In applications such as cryptology, the shift register can be preset to a known initial condition. but in general they are either set to all zeros except for one bit, or set to all ones except for one bit.
In an LFSR, the bits contained in selected positions in the shift register are combined in some sort of function and the result is fed back into the register's input bit. By definition, the selected bit values are collected before the register is clocked and the result of the feedback function is inserted into the shift register during the shift, filling the position that is emptied as a result of the shift.
For example, in an LFSR with an XOR gate, the feedback input is created by adding the selected bit values. If the sum is odd, the feedback input is one; otherwise the input is zero. If XORs are used to generate the feedback input to the shift register, then the state of all zeros is not allowed as the system would never leave the all zero state. If XNORs are used, then the state of all ones is not allowed for the same reasons. The choice largely depends on how the LFSR is being implemented.
The bit positions selected for use in the feedback function are called “taps.” The list of the taps is known as the “tap sequence.” By convention, the output bit of an LFSR that is n bits long is the nth bit; the input bit of an LFSR is bit 1.
LFSR are not truly random devices because after a certain number of cycles, the cycle out of the LFSR will repeat, hence they are termed “pseudo-random devices.” The maximum number of cycles before the cycle repeats can be determined by the formula: 2n−1, where n represents the number of flip-flops. The term 2n−1 comes from the fact that either the all-zero or all-one state is disallowed.
The placement of the XOR/XNOR taps determine the bit sequence of the noise generated. A poor selection of taps can lead to a LFSR that has a cycle length much less than the 2n−1 maximum.
The numbers below show the hexadecimal value out of a 17-bit LFSR initialized to a value of 10000 shifting right for the first 64 cycles:                10000, 08000, 04000, 02000, 01000, 00800, 00400, 00200, 00100, 00080, 00040, 00020, 10010, 08008, 04004, 02002, 01001, 10800, 08400, 04200, 02100, 01080, 00840, 00420, 10210, 08108, 04084, 02042, 01021, 00810, 00408, 00204, 00102, 00081, 10040, 08020, 14010, 0A008, 05004, 02802, 01401, 10A00, 08500, 04280, 02140, 010A0, 10850, 08428, 14214, 0A10A, 05085, 12842, 09421, 04A10, 02508, 01284, 00942, 004A1, 00250, 10094, 0804A, 04025, 02012 . . .        
The most important properties of an LFSR are that it has a low (constant) gate delay, and more importantly, if the taps are chosen properly, repeated shifting (starting with any non-zero value) will cycle through every possible non-zero value of the register. A 55-bit maximal-length LFSR would create over 255−1 patterns that, at a 1-GHz clock rate, would take roughly a year to generate the whole pattern set. The problem with the LFSR counter is that is not possible to derive the decimal value of the count from the LFSR's value—direct enumerative simulation is required which is often problematic due to the long simulation times required.
Therefore, while a long-period counter using an LFSR is fast and does not use a large amount of logic gates, the counter, due to its pseudorandom nature, does not produce useful numbers for counting. All LFSR counters suffer from this and are not best-suited for use as long-period counters.